翻訳と辞書 Words near each other ・ Ydessa Hendeles ・ YDG SRA protein domain ・ YDG-H ・ Ydin ・ Yding Skovhøj ・ YDL ・ YDN ・ Ydre Municipality ・ Ydre Nørrebro ・ Ydre Østerbro ・ Ydrefors ・ Ydrissa M'Barke ・ Ydrousa ・ YDS ・ YDS (Language Proficiency Test administered in Turkey) ・ YDS algorithm ・ Ydstebøhavn ・ YDT ・ Ydw Valley and Fron Road Geological Exposures ・ Ye ・ Ye (ancient China) ・ Ye (Cyrillic) ・ Ye (pronoun) ・ Ye (surname) ・ Ye Antient Order of Noble Corks ・ Ye Antientist Burial Ground, New London ・ Ye Chenghai ・ Ye Chengzhong ・ Ye Chong ・ Ye Chongqiu Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク YDS algorithm ： ウィキペディア英語版 YDS algorithm YDS is a scheduling algorithm for dynamic speed scaling processors which minimizes the total energy consumption. It was named after and developed by Yao et al.〔F.F. Yao, A.J. Demers and S. Shenker. A scheduling model for reduced CPU energy. Proc. 36th IEEE Symposium on Foundations of Computer Science , 374–382, 1995.〕 There is both an online and an offline version of the algorithm. ==Offline Algorithm== Definitions: * There is a set of n Jobs $J\; :=\; J\_1,\; ...,\; J\_n$, where each job $J\_i$ has a release time $r\_i$, deadline $d\_i$ and a processing volume $w\_i$. * $I$ is a certain time interval. * Also we have $\backslash Delta\_I\; =\; \backslash frac\; \backslash sum\_\; w\_i$, the work density in $I$. * And finally $S\_I\; \backslash in\; J$ is the set of Jobs that that must be processed in $I$, that means Jobs with $(d\_i)\; \backslash in\; I$. The algorithm then works as follows: :While $J\; \backslash neq\; \backslash$ ::Determine the time interval $I$ of maximum density $\backslash Delta\_I$. ::In $I$ process the jobs of $S\_I$ at speed $\backslash Delta\_I$ according to EDF ::Set $J\; :=\; J\; \backslash setminus\; S\_I$. ::Remove $I$ from the time horizon and update the release times and deadlines of unscheduled jobs accordingly. :end While In other terms it's a recursive algorithm that will follow these steps until all jobs are scheduled: # Calculate all intensities for all possible combinations of intervals. This means that for every start time and end time combination the intensity of work is calculated. For this the times of all jobs whose arrival time and deadline lie inside the interval are added and divided by the interval length. To speed up the process, only combinations of arrival times and later deadlines need to be considered, as times without arrival of a process or deadline can be shrunk to a smaller interval with the same processes, thus increasing intensity, and negative intervals are invalid. Then the maximum intensity interval is selected. In case of multiple equally intense intervals, one can be chosen at will, as intensities of non-overlapping intervals do not influence each other, and removing a part of an interval will not change the intensity of the rest, as processes are removed proportionally. # The processes inside this interval are scheduled using Earliest Deadline First, meaning that the job inside this interval whose deadline will arrive soonest is scheduled first, and so on. The jobs are executed at the above calculated intensity to fit all jobs inside the interval. # The interval is removed from the timeline, as no more calculations can be scheduled here. To simplify further calculations, all arrival times and deadlines of remaining jobs are recalculated to omit already occupied times. For example, assume a job $A$ with arrival time $a\_A\; =\; 0$, deadline $d\_A\; =\; 10$ and a workload $w\_A\; =\; 5$, and a job $B$ with $a\_B\; =\; 5$, $d\_B\; =\; 10$ and $w\_B\; =\; 4$. Assume the previous interval was from time $3$ to $8$. To omit this interval the times of $A$ and $B$ need to be adjusted; workloads are unaffected, as no work has been done for either $A$ or $B$. $a\_A$ stays the same, as it's unaffected by later omissions. $d\_A$, however, needs to be changed to $5$, as $10\; -\; (8\; -\; 3)\; =\; 5$. This is the time job $A$ has left before its deadline. The arrival time $a\_B$ becomes $3$, as it would have been inside the removed interval. $d\_B$ also becomes $5$, as the time left after the removed interval is $2$. It is important, however, to remember the actual arrival and deadline times for later assembly of the scheduling. # Repeat steps 1-3 until all jobs have been scheduled. # Assemble jobs into final scheduling according to their allotted time intervals. Remember, though, that an interval may be split in two by another interval calculated earlier. For any Job instance, the algorithm computes an optimal schedule minimizing the total energy consumption.〔Susanne Albers , ("Algorithms for Dynamic Speed Scaling" )〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「YDS algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.